home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / amok_lha / amok07.lha / List / List.doc < prev    next >
Encoding:
Text File  |  1993-08-16  |  8.9 KB  |  317 lines
  1.                          L i s t
  2.                          =======
  3.  
  4. Documentation for module List
  5.  
  6. Author: Michael Frieß [mif]
  7.         Kernerstr. 22a
  8.         7000 Stuttgart 1
  9.  
  10. Copyright remarks
  11. -----------------
  12.  
  13. (C) Copyright 1988 by Michael Frieß. All rights reserved.
  14. The whole package (see chapter package) is public domain.
  15. All (source, documentation and code) is freely redistributable,
  16. as long as my name and the copyright notices remain intact, and
  17. only for non-commercial use. That means you can give it away, but
  18. don´t sell it.
  19. Commercial use without my explicit, written permission is not
  20. allowed. Contact me to get it and, perhaps, to pay some fee.
  21.  
  22. Improvements and new ideas are welcome, as long as the changes are
  23. good documented inline and in the documentation files. I´would like
  24. to know, if you make major changes and repost it.
  25.  
  26.  
  27. Contents
  28. --------
  29.  
  30.  Package
  31.  Introduction
  32.  Generic Data Types
  33.  New Data Type "List"
  34.  List-Operators
  35.  Example of Use
  36.  What was my intention?
  37.  Further generic types
  38.  Referenced Literature
  39.  
  40. Package
  41. -------
  42.  
  43. The whole package "List" consist of following files:
  44.  
  45.   List.doc        This documentation file
  46.   List.dok        German documentation
  47.   List.def        Definition module
  48.   List.mod        Implementation module
  49.   List.sym        Symbol file
  50.   List.obj        Compiled object code
  51.   TestOfList.mod  Test module (source)
  52.   TestOfList      Test module in executable form
  53.  
  54.  
  55. Introduction
  56. ------------
  57.  
  58. Often you need basic data structures and operations on
  59. them, which are not implemented in Modula-II.
  60. But Modula-II supports development of generic data types.
  61. The best known example of generic data type is "File".
  62. You can import File and procedures operating on it from
  63. system module "FileSystem".
  64. The one thing, you have to know, is the abstract concept
  65. of files, not the realization.
  66. This module offers a generic type "List". So you have not
  67. to reinvent wheel, e.g. program your own list by pointers,
  68. every time, you need one. You just have to know the
  69. abstract concept of lists.
  70.  
  71.  
  72. Generic Data Types
  73. ------------------
  74.  
  75. In Modula-II (as well as in most other high-level languages)
  76. you can create new types by declaration. New types can consist
  77. of structures and components, but every component type have to
  78. be known before declaration of the new type (either by
  79. declaration or as an simple data type - for example BOOLEAN).
  80. Modula-II knows four structure methods for building new types:
  81. ARRAY, SET, RECORD and POINTER.
  82. With last one you can create a large scale of new types.
  83. For example a list:
  84.   TYPE  listptr = POINTER TO list;
  85.         list    = RECORD
  86.                    item : T0;
  87.                    next : listptr
  88.                   END;
  89.  
  90. To use this list you develop some procedures for initialization,
  91. insert an item, read an item and so on. All procedures are
  92. independent of your component type T0, but your type "list"
  93. depends on it.
  94. A generic data type now can be used with every(!) component
  95. type!
  96. The concept of Modula-II supports development of modules that
  97. present data capsules exporting a generic type and procedures
  98. working on it.
  99.  
  100.  
  101. New Data Type "List"
  102. --------------------
  103.  
  104. The generic type "List" is a sort of linear list with only
  105. sequential access. Linear means that one element follows the
  106. other (as in a queue!), sequential means that the list can be
  107. inspected only by go from one element to its succeedor.
  108. In opposite to a sequence (I refer to [1]) data can also be
  109. inserted into list, not only appended at the end.
  110.  
  111.  
  112. List-Operators
  113. --------------
  114.  
  115. In following operators and their abstract intention are listed.
  116. You can find more details in definition module.
  117.  
  118. o Init
  119.   Initialize a new empty list for further use.
  120.  
  121. o Discard
  122.   Discard a list, i.e. all elements and the list itself, and frees
  123.   memory allocation.
  124.  
  125. o Insert
  126.   insert a new element to the given list. Insertion can be done at
  127.   list´s end or behind current element.
  128.  
  129. o Write
  130.   overwrites content of the current element or appends an element, if
  131.   executed on end of the given list.
  132.  
  133. o Reset
  134.   sets current element to beginning of the given list.
  135.  
  136. o Read
  137.   gets content of current element and next element becomes current
  138.   element for further inspections.
  139.  
  140. o Delete
  141.   deletes current element and frees its memory allocation.
  142.  
  143. o End
  144.   determines, whether end of list is reached.
  145.  
  146. o Do
  147.   executes a specific action (given by parameter) on whole list or a
  148.   part of it. "Do" begins with current element and terminate at end
  149.   of the given list or by special end indicated by the user defined
  150.   action.
  151.  
  152.  
  153. Example of Use
  154. --------------
  155.  
  156. Using the type list is very simple:
  157.  
  158. 1) Import list and needed operators:
  159.  
  160.    FROM List IMPORT list, Init, Insert, Read, Reset, Discard ...;
  161.  
  162. 2) Define your element type:
  163.    (for example:)
  164.  
  165.    TYPE address = RECORD
  166.                     name, prename
  167.                     street,
  168.                     city         : ARRAY [1..30] OF CHAR;
  169.                     country      : CHAR
  170.                   END;
  171.  
  172. 3) Define a list variable and a variable containing your data:
  173.  
  174.    VAR l       : list;
  175.        Address : address;
  176.  
  177. 4) Initialize list l:
  178.  
  179.    Init (l);
  180.  
  181.    (or with qualified export/import:)
  182.  
  183.    List.Init (l);
  184.  
  185. 5) Insert data:
  186.  
  187.    WITH Address DO
  188.     name    := "Kant";
  189.     prename := "Immanuel";
  190.     street  := "Alte Mühlengasse 5";
  191.     city    := "Leipzig";
  192.     country := "G"; (* Germany *)
  193.    END;
  194.    Insert (l, Address);
  195.  
  196.    inserting further addresses for example by reading from file or user
  197.    input
  198.  
  199. 6) Reset list l for reading the content:
  200.  
  201.    Reset (l);
  202.  
  203. 7) Read one element:
  204.  
  205.     Read (l, Address);
  206.  
  207.    or all elements:
  208.  
  209.     WHILE NOT End(l) DO
  210.      Read (l, Address);
  211.      - Display Address -
  212.     END;
  213.  
  214.    or display all elements by define a procedure "Display" to
  215.    display one address and use the imported procedure "Do":
  216.  
  217.     Reset (l); (* begin with top of list *)
  218.     Do (l, Display);
  219.  
  220. 8) Discard the list after use:
  221.  
  222.    Discard (l);
  223.  
  224.  
  225. Easy, isn´t it?
  226.  
  227.  
  228. What was my intention?
  229. ----------------------
  230.  
  231. I wanted to understand how to implement generic data types and general
  232. operators in a module as a data capsule. Now I tried to present you
  233. these (not even newest) concepts of programming:
  234.  
  235. o information hiding
  236.   The items exported by the module can be used without knowing
  237.   implementation. It´s a way of abstraction, what is important for
  238.   large programs. Modula-II supports this by the concept of modules.
  239.  
  240. o data capsule
  241.   The new data type and all features (operators, functions,
  242.   procedures and so on) are surrounded by one module containing them
  243.   like a capsule. You can only access objects of the new type by
  244.   the given operators.
  245.  
  246. o opaque type
  247.   Another feature of Modula-II, the opaque type, is used for
  248.   information hiding. The compiler M2Amiga allows only pointer types
  249.   to be opaque, but probably other compilers will do same way.
  250.  
  251. o generic type
  252.   A data type (data structure) is possible to be used with any element
  253.   type.
  254.   Caution: Implementation of generic types is possible in Modula-II,
  255.   but no more type compatibility check is possible, because the
  256.   unspecified type ARRAY OF WORD (or ARRAY OF BYTE in M2Amiga) is
  257.   used for indicating the element type.
  258.  
  259. o procedure type
  260.   Procedure type in Modula-II is a powerful tool for software
  261.   development. In this case it is used for separation of actions, that
  262.   are executed on different data.
  263.   One data represents the whole list - the other represents one
  264.   element. So action on the whole list is implemented in module
  265.   List, the other one manipulating the element data is user defined.
  266.   Remark similarity of action and data!
  267.   In case of M2Amiga it seems not to be possible to deactivate
  268.   parameter check while compiling and there is no other way to use
  269.   a generic parameter in a procedure type (Hey, what about some
  270.   improvements of the language, so Modula-III?).
  271.   The test module demonstrates the way you can use a generic parameter,
  272.   but it doesn´t satisfy me.
  273.  
  274.  
  275. Further generic types
  276. ---------------------
  277.  
  278. I have implemented other generic data types:
  279.  
  280.   o queue
  281.     a simple FIFO-list
  282.  
  283.   o stack
  284.     a simple LIFO-list
  285.  
  286.   o AVL-Tree
  287.  
  288. Surely there are a lot of other possible generic types:
  289.  
  290.   o pipe
  291.     There is a pipe-handler at a fish-disk (I don´t know the number).
  292.     I would enjoy an implementation of a pipe-handler with whole
  293.     Modula-II support as a generic type.
  294.     The great advantage of a pipe is the simultaneous use by multiple
  295.     processes. For example two processes write data into the pipe and
  296.     one process reads data simultaneous.
  297.     (I´m looking forward the module for fully support of amiga´s multi-
  298.      tasking operating system!)
  299.  
  300.   o BTree
  301.     Another sort of tree also described in [1].
  302.  
  303.   o Hash-Table
  304.     Perhaps a hash-table is also a candidat for generic data type -
  305.     I haven´t thought about it yet.
  306.  
  307. I´m looking forward a lot of other implementations of generic data
  308. types. For free distribution on AMOK-Disks send your implementations
  309. to my address or just to any address of an AMOK-member.
  310.  
  311.  
  312. Referenced literature
  313. ---------------------
  314.  
  315. [1] N.Wirth "Algorithmen und Datenstrukturen mit Modula-II"
  316.     Teubner, Stuttgart 1986
  317.